home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / wais / waisgate / hash.c < prev    next >
C/C++ Source or Header  |  1995-05-09  |  16KB  |  549 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4. */
  5.  
  6. /* Hash Table routines
  7.  * for strings based on Common Lisp interface functions.
  8.  *  -brewster
  9.  */
  10.  
  11. /* This hashtable will never grow, rather it just adds entries to the buckets.
  12.  * 
  13.  * The contents are all in one contiguous block so that the contents can be 
  14.  * sorted.  This will cause problems because of the reallocs needed.
  15.  *
  16.  */
  17.  
  18. /* Change log:
  19.  * $Log:    hash.c,v $
  20.  * Revision 1.9  92/05/06  17:27:38  jonathan
  21.  * Added cast for htable->contents malloc.
  22.  * 
  23.  * Revision 1.8  92/02/21  11:06:53  jonathan
  24.  * Added header, RCSIdent.
  25.  * 
  26.  * Revision 1.7  92/02/16  12:37:57  jonathan
  27.  * Changed bzero's to memset's.
  28.  * 
  29.  * Revision 1.6  92/02/12  13:20:08  jonathan
  30.  * Added "$Log" so RCS will put the log message in the header
  31.  * 
  32. */
  33.  
  34. /* Cool things we could do from here:
  35.      A) Use a signature to see if the word is in the hashtable, so that
  36. get_hash will return NULL very quickly for the new words.  This will reduce
  37. the number of times a whole bucket must be searched.  This might not help
  38. much since the file that I was indexing had 8M words, and only 350k
  39. different words, so there are 1 NULL in 30 requests expected. Therefore,
  40. unless searching down a list of buckets takes a long time, this is not a
  41. big problem.  The only case I can think of is if it induces paging.
  42.     B) Since the most recently accessed entry of the hashtable is at the
  43. front, we can sort the hashtable entries so that the heads of all the
  44. buckets are clumped, so that hopefully these will stay in memory, and the
  45. infrequently used ones would move to the paged out space.
  46. */
  47.  
  48. #ifndef lint
  49. static char *RCSid = "$Header: /tmp_mnt/net/quake/proj/wais/wais-8-b5/ir/RCS/hash.c,v 1.9 92/05/06 17:27:38 jonathan Exp $";
  50. #endif
  51.  
  52. #include "cdialect.h"
  53. #include "cutil.h"
  54. #include "hash.h"
  55. #include <string.h>
  56. #include "panic.h"
  57.  
  58. #define ALIGNMENT_SIZE 4 /* the word size to align elements of the contents on */
  59.  
  60.  
  61. hashtable*
  62. make_hashtable (number_of_buckets, number_of_elements, element_size)
  63.      long number_of_buckets;
  64.      long number_of_elements;
  65.      long element_size;
  66. {
  67.   hashtable *htable = (hashtable *)s_malloc(sizeof(hashtable));
  68.  
  69.   if(number_of_buckets > 0)
  70.     htable->number_of_buckets = number_of_buckets;
  71.   else
  72.     htable->number_of_buckets = DEFAULT_NUMBER_OF_BUCKETS;
  73.  
  74.   htable->buckets_mask = htable->number_of_buckets - 1;
  75.  
  76.   if(element_size > 0){
  77.     htable->element_size = element_size;
  78.   }
  79.   else
  80.     return(NULL);
  81.   
  82.   htable->number_of_elements = 0;
  83.  
  84.   if(number_of_elements > 0)
  85.     htable->max_number_of_elements = number_of_elements;
  86.   else
  87.     htable->max_number_of_elements = DEFAULT_NUMBER_OF_ELEMENTS;
  88.  
  89.   htable->buckets
  90.     = (long*)s_malloc(sizeof(long) * htable->number_of_buckets);
  91.   /* this depends on -1L to be made up of -1 characters */
  92.   memset(htable->buckets, -1, sizeof(long) * htable->number_of_buckets);
  93.  
  94.   htable->contents 
  95.     = (hash_entry*)s_malloc(htable->max_number_of_elements * 
  96.                 htable->element_size);
  97.   return(htable);
  98. }
  99.  
  100.  
  101. /*----------------------------------------------------------------- */
  102.  
  103. /* returns a hashcode for a string.  
  104.  * key is a string that is assumed to be downcased (if appropriate),
  105.  * function is a number from 0 to 20 that are fairly independent hash 
  106.  *    functions.
  107.  */
  108.  
  109.  
  110. /*===========================*
  111.  *===  Hashing Functions  ===*
  112.  *===========================*/
  113.  
  114.  
  115. /*___________________________________________________________________________*/
  116.  
  117. /* Date: Fri, 13 Dec 91 16:28:53 EST
  118.    From: Henry Massalin <henry@cs.columbia.edu> */
  119.  
  120. #define reg    register
  121.  
  122. hash(s)
  123. reg    unsigned char    *s;
  124. {
  125.   reg    int        c;
  126.   reg    unsigned long    h = 0;
  127.   extern    unsigned long    RandHash[];
  128.  
  129.   if((h = (unsigned long)*s++) == 0)
  130.     return(h);
  131.   while((c = *s++) != 0)
  132.     h += RandHash[ 0xFF & ((h >> 24) ^ c )];
  133.   return(h);
  134. }
  135.  
  136. /*___________________________________________________________________________*/
  137.  
  138. /*
  139.  * Almost any random permutation will work.  Of course, now that I've
  140.  * picked this one, everyone else must use it also, to be consistent.
  141.  *
  142.  * This array is constructed from four independent permutations of the
  143.  * integers 0..255.  A different permutation in each of the bytes.
  144.  */
  145. unsigned long
  146.     RandHash[256] = {
  147.     0x4BEF74B7,0x7FE1F5A6,0xB4C08BF6,0xC2CF0CD0,
  148.     0x788E2A29,0xB043B6B9,0x5B56C90C,0x324D8FE7,
  149.     0x8D9C854A,0xCAE06AC8,0x902076A1,0x949EAA31,
  150.     0xDC070A08,0xF7499B6D,0x17883EAA,0x22A65A35,
  151.     0x34FC6407,0x8322F367,0xD105BB0F,0xD8A29526,
  152.     0x8A1B708A,0xBE85B1E1,0xC66AC334,0xC1B13A1C,
  153.     0xEDF644E4,0x3EA3806C,0x2732D31D,0xEBF504A9,
  154.     0x08BB2B52,0x4775992C,0x3C0B8CF7,0x5FA0AEA2,
  155.     0x7616D761,0x66AA86DB,0xC73305C0,0x09E6EA99,
  156.     0xC9789DD6,0xF47340F1,0x3941303E,0x7542233A,
  157.     0xE0812ED1,0xFF2E54FE,0x07B887EB,0x68CD0E93,
  158.     0xB124C17F,0xD01A9C5B,0x96B490ED,0xA7CAE5FC,
  159.     0x18D41F37,0x6E8DA1BC,0x9B631940,0x35ABCFD4,
  160.     0xACA1FB0A,0x2F71B921,0x6F10A747,0xA6680796,
  161.     0x01F12271,0xFDBE0378,0x02F0FF79,0xEC3FF2D2,
  162.     0x84485C9C,0x60BF9113,0x98CC35E3,0xAA2A8D4D,
  163.     0xA5CBA2E9,0xF0AE1EF2,0x990118E2,0x64A966F5,
  164.     0x8595490D,0x7E9B4391,0xE8311B7D,0x2474BCBF,
  165.     0x19D6E286,0xDFD32D5C,0xAB5116CA,0x7D72D6D5,
  166.     0x0BF44F5E,0x6170B3D3,0x2C471CC2,0x2EFD1118,
  167.     0x8C878836,0x62FE52E0,0x2B8C1277,0x2ACEBDEC,
  168.     0xB2E8A8A3,0x30B757AE,0x708BBA8D,0x501EF654,
  169.     0x49A7EF1E,0xFE7636AD,0xB54BBE4F,0x1ADBDB8C,
  170.     0x72E24DD9,0xF68A2517,0xF56FEEDF,0x5A7EB75D,
  171.     0xD606F9E6,0xC32526B8,0x5EB613F3,0x0C08CBDE,
  172.     0x8B965E59,0xB361EB75,0x3FADE465,0xB8FFD16F,
  173.     0x26442988,0x00D2D830,0x3D58FE41,0x3B386E44,
  174.     0x1297E914,0xAFC11083,0xC5EBE8B6,0x15A49ECD,
  175.     0xF950C263,0xA0DA0982,0x4CBDF101,0xE227F77E,
  176.     0x556DB8DA,0xA1BA2125,0x1E3BD409,0xFCF25155,
  177.     0x110A983B,0x7B7F1A4C,0xE7FB4C69,0xC8994E1F,
  178.     0x586C4A42,0x5C1FAF2F,0xAD777D48,0x9186696B,
  179.     0xD52181B4,0xE94C39EF,0x9EDEB2FF,0x802FDA20,
  180.     0xA228D902,0x52BC7CFD,0x53DD47AC,0x6D12D25F,
  181.     0xCE1D6D8F,0xF12C8E2B,0xDD5700C1,0x9A402851,
  182.     0x386E53D7,0x0DF88281,0x4A55CDC4,0x653692B0,
  183.     0x203CAC8E,0x747C6164,0xC47A02B2,0x1B4FC82D,
  184.     0xF8934B7A,0x36A82CB5,0x690CD080,0x2800A524,
  185.     0x1C045D0E,0xBF09CAF0,0x8814ABB3,0xE3D0776A,
  186.     0x219AA6D8,0xCC375653,0xFA2327A8,0x57F75F27,
  187.     0x732DA903,0x8F696738,0x3A453223,0xDA1C9F32,
  188.     0xCF90152A,0x0F64BFF4,0xD7533FA5,0x8E7D55DC,
  189.     0xBC598998,0x45110DBA,0x4D92E6FB,0x7746C01A,
  190.     0x951348A0,0xBBFA7E9B,0x055EAD7B,0x06B36BBB,
  191.     0x0EE31D97,0x37297F11,0xEF529450,0x51C6E168,
  192.     0x1F67C63F,0x6B023443,0x449F5BFA,0x48C39A4B,
  193.     0xD30E426E,0x0ADFE31B,0x467B6085,0x7CC49676,
  194.     0x140DFA60,0xE16B7274,0x235AEC05,0xD2D7DCC6,
  195.     0x13946212,0x339D2462,0xFB82F8EE,0xB6197970,
  196.     0xBD0F3C9D,0xE64E3B28,0xE4B07A87,0x54C92F95,
  197.     0x6CC583AB,0xD4182015,0x86DC755A,0xA930A333,
  198.     0x82B273EA,0x923EED7C,0xF354A02E,0xEEEEA439,
  199.     0x1D89089A,0xD9EDDEE8,0x1017B504,0xA45CB0C7,
  200.     0x93C7E0A4,0x43D95858,0xDB654594,0x31D578CF,
  201.     0xCDF98489,0xB915C7F9,0x67846FE5,0x04D150AF,
  202.     0x5DF314DD,0xCB911772,0xA8627156,0x258FC573,
  203.     0xEAA5E79F,0x633D4119,0x793501C9,0x7AD80F0B,
  204.     0x4E5DF04E,0x97AF6884,0xAE3A9745,0xA3ACF48B,
  205.     0x16398A10,0xDE8346C3,0x42C20606,0x03EAB4B1,
  206.     0x8798FDCC,0x9CE4FC22,0x81B5DD3D,0x563431BE,
  207.     0x2D799349,0xF2036C92,0xB7E97B3C,0x71E559C5,
  208.     0x5960C4BD,0x295B63F8,0xBA5F0B57,0xE5B93DCE,
  209.     0x6A4ACC90,0x89EC6516,0x4180D566,0x40263300,
  210.     0x9DE738CB,0x4F2B3746,0x9F66DF9E,0xC0C8CEA7
  211. };
  212.  
  213. /*___________________________________________________________________________*/
  214.  
  215. /*
  216.  * Create permutations
  217.  */
  218. #if 0
  219. #define N        256
  220. #define    ulong        unsigned long
  221.  
  222. main()
  223. {
  224.     int     i, j;
  225.     ulong    p[N], q[N];
  226.  
  227.     permute(p);
  228.     for(i=3; --i >= 0; ) {
  229.         permute(q);
  230.         for(j=N; --j >= 0; )
  231.             p[j] = (p[j] << 8) + q[j];
  232.     }
  233.  
  234.     printf("ulong    RandHash[%d] = {", N);
  235.     for(i=0; i<N; i++)
  236.         printf("%s0x%08X", ((i&3) ? "," : "\n\t"), p[i]);
  237.     printf("\n};\n\n");
  238. }
  239.  
  240. permute(p)
  241. ulong    *p;
  242. {
  243.     int     i, r, t;
  244.  
  245.     /* initialize array */
  246.     for(i=N; --i >= 0; )
  247.         p[i] = i;
  248.  
  249.     /* generate random permutation */
  250.     for(i=N; --i >= 0; ) {
  251.         r = (i * (random() & 0xFFFF)) >> 16;
  252.         t = p[r]; p[r] = p[i]; p[i] = t;
  253.     }
  254. #if 0
  255.     /* make sure there are no cycles of len < N */
  256.     for(i=N; --i >= 0; ) {
  257.     }
  258. #endif
  259. }
  260.  
  261. #endif
  262.  
  263. /* --------------------------- */
  264.  
  265. #ifdef UNUSED
  266.  
  267. /* courtesy ses@ccgr.technion.ac.il, but it turns out in
  268.    informal timings that it increases the index time.  sigh. */
  269.  
  270. static char coeff[] = {
  271.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  272.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  273.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  274.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  275.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  276.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  277.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  278.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
  279.  
  280.  
  281. long hash_code(key, function)
  282.      char *key;
  283.      long function;
  284. {
  285.   register char *foo;
  286.   register long hash = 0;
  287.   register int l;
  288.  
  289.   for(l=function,foo=key;l<sizeof(coeff) && *foo ;l++)
  290.     hash = hash + (*(foo++) * coeff[l]);
  291.  
  292.   return(hash);
  293. }
  294.  
  295. #endif /* def UNUSED   */
  296.  
  297.  
  298. /*----------------------------------------------------------------- */
  299.  
  300. #define HASHTABLE_GROW_FACTOR 4
  301.  
  302. hash_entry *put_hash(key, htable, element)
  303.      char *key;
  304.      hashtable *htable;
  305.      hash_entry *element;
  306. {
  307.   /* allocate the entry out of the contents area, then add the entry to 
  308.      the head of the bucket list. */
  309.  
  310.   /* old long bucket_number = hash_code(key, 0) & htable->buckets_mask; */
  311.   long bucket_number = hash((unsigned char*)key) & htable->buckets_mask;
  312.   long old_bucket_value =  (htable->buckets)[bucket_number];
  313.   long new_bucket_value = htable->number_of_elements++;
  314.   hash_entry *entry_header;
  315.  
  316.   if(new_bucket_value >= htable->max_number_of_elements){
  317.     long new_size = 
  318.       HASHTABLE_GROW_FACTOR * htable->max_number_of_elements * 
  319.     htable->element_size;
  320.     
  321.     waislog(WLOG_LOW, WLOG_INFO, 
  322.         "Expanding hashtable from %ld bytes to %ld bytes address %ld...",
  323.        htable->max_number_of_elements * htable->element_size ,
  324.        new_size, htable->contents);
  325.     htable->max_number_of_elements *= HASHTABLE_GROW_FACTOR;
  326.     htable->contents = (hash_entry*)s_realloc(htable->contents, new_size);
  327.     if(NULL == htable->contents)
  328.       panic("Out of virtual memory.");
  329.   }
  330.   entry_header = &(htable->contents)[new_bucket_value];
  331.   memcpy((char *)entry_header, (char *)element, htable->element_size);
  332.   /* printf("Writing key: '%s' into index %ld\n", key, new_bucket_value); */
  333.   strncpy(entry_header->key, key, MAX_KEY_SIZE + 1); 
  334.   entry_header->next = old_bucket_value;
  335.  
  336.   (htable->buckets)[bucket_number] = new_bucket_value;
  337.   return(entry_header);
  338. }
  339.  
  340. /*----------------------------------------------------------------- */
  341.  
  342. /* returns a pointer to the element stored or NULL if none. */
  343. hash_entry *get_hash (key, htable)
  344.      char *key;
  345.      hashtable *htable;
  346. {
  347.   /* this looks up the value in the bucket and puts it at the head of the 
  348.      bucket. */
  349.  
  350.   /* old long bucket_number = hash_code(key, 0) & htable->buckets_mask; */
  351.   long bucket_number = hash((unsigned char*)key) & htable->buckets_mask;
  352.   long old_bucket_value =  (htable->buckets)[bucket_number];
  353.  
  354.   long next_contents_index = old_bucket_value;
  355.  
  356.   while(next_contents_index != -1){
  357.     /* keep looking down the list for the right value */
  358.     if(0 == strcmp((htable->contents)[next_contents_index].key, 
  359.            key))
  360.       /* found it */
  361.       return(&(htable->contents)[next_contents_index]);
  362.     else
  363.       next_contents_index = (htable->contents)[next_contents_index].next;
  364.   }
  365.   return(NULL);
  366. }
  367.   
  368.  
  369. /*----------------------------------------------------------------- */
  370.  
  371. boolean clr_hashtable (htable)
  372.      hashtable *htable;
  373. {    
  374.   htable->number_of_elements = 0;
  375.   memset(htable->buckets, -1, sizeof(long) * htable->number_of_buckets);
  376.   return(true);
  377. }
  378.  
  379. /*----------------------------------------------------------------- */
  380.  
  381. /* removes contents and free's memory for the hastable.   
  382.    returns true if successful, false otherwise */
  383. boolean free_hashtable(htable)
  384.      hashtable *htable;
  385. {
  386.   s_free(htable->contents);
  387.   s_free(htable->buckets);
  388.   s_free(htable);
  389.   return(true);
  390. }
  391.  
  392. /*----------------------------------------------------------------- */
  393.  
  394. /* returns the number of elements in the hashtable */
  395. long hashtable_count(htable)
  396.      hashtable *htable;
  397. {
  398.   return(htable->number_of_elements);
  399. }
  400.  
  401. /*----------------------------------------------------------------- */
  402.  
  403.  
  404. static int hash_entry_compare _AP((hash_entry*i,hash_entry* j));
  405.  
  406. static int hash_entry_compare(i,j)
  407. hash_entry *i;
  408. hash_entry *j;
  409. {
  410.   return(strcmp(i->key, j->key));
  411. }
  412.  
  413.  
  414. boolean sort_hashtable(htable)
  415.      hashtable *htable;
  416. {
  417.   qsort(htable->contents,
  418.     htable->number_of_elements,
  419.     (size_t)sizeof(hash_entry),
  420.     hash_entry_compare);
  421.   return(true);
  422. }
  423.  
  424. /*----------------------------------------------------------------- */
  425. /* print routines */
  426.  
  427.  
  428. static void print_content_element(index, htable)
  429.      long index;
  430.      hashtable *htable;
  431. {  
  432.   printf("  Index: %ld, key: '%s', Next index %ld\n", 
  433.      index, (htable->contents[index]).key, 
  434.      (htable->contents[index]).next);
  435. }
  436.  
  437. void print_bucket(bucket, htable)
  438.      long bucket;
  439.      hashtable *htable;
  440. {
  441.   long next_contents_index = (htable->buckets)[bucket];
  442.  
  443.   printf(" Bucket: %ld\n", bucket);
  444.   while(next_contents_index != -1){
  445.     hash_entry * entry_header = &(htable->contents)[next_contents_index];
  446.     print_content_element(next_contents_index, htable);
  447.     next_contents_index = entry_header->next;
  448.   }
  449.   return;
  450. }
  451.  
  452. long bucket_length(bucket, htable)
  453.      long bucket;
  454.      hashtable *htable;
  455. {
  456.   long next_contents_index = (htable->buckets)[bucket];
  457.   long answer = 0;
  458.   while(next_contents_index != -1){
  459.     answer++;
  460.     next_contents_index = ((htable->contents)[next_contents_index]).next;
  461.   }
  462.   return(answer);
  463. }
  464.  
  465. static int bucket_length_compare _AP((long*i,long* j));
  466.  
  467. static int bucket_length_compare(i,j)
  468. long *i;
  469. long *j;
  470. {
  471.   return((*j) - (*i));
  472. }
  473.  
  474. void analyze_hashtable_distribution(htable)
  475.      hashtable * htable;
  476. {
  477.   long count = 0;
  478.   long max_length = 128;
  479.   long *bucket_length_array = (long *)malloc(sizeof(long) * max_length);
  480.   memset((char*)bucket_length_array, 0, (sizeof(long) * max_length));
  481.  
  482.   waislog(WLOG_LOW, WLOG_INFO, "--Hashtable Analysis--");
  483.   waislog(WLOG_LOW, WLOG_INFO, "Number of buckets: %ld",
  484.       htable->number_of_buckets);
  485.   waislog(WLOG_LOW, WLOG_INFO, "Number of allocated elements %ld",
  486.       htable->number_of_elements);
  487.   waislog(WLOG_LOW, WLOG_INFO, "Max number of elements %ld",
  488.       htable->max_number_of_elements);
  489.  
  490.   while(count < htable->number_of_buckets){
  491.     long length = bucket_length(count, htable);
  492.     if(length > max_length){  /* too small, start again */
  493.       max_length *= 2;
  494.       free((char*)bucket_length_array);
  495.       bucket_length_array = (long *)malloc(sizeof(long) * max_length);
  496.       memset((char*)bucket_length_array, 0, (sizeof(long) * max_length));
  497.       count = 0;
  498.     }
  499.     else{
  500.       bucket_length_array[length]++;
  501.       count++;
  502.     }
  503.   }
  504.   /* print the buckets */
  505.   for(count = 0; count < max_length; count++){
  506.     if(bucket_length_array[count] > 0){
  507.       waislog(WLOG_LOW, WLOG_INFO, "Length %4ld, number of buckets: %5ld.",
  508.           count, bucket_length_array[count]);
  509.     }
  510.   }
  511.   free((char*)bucket_length_array);
  512. }
  513.  
  514. void print_hashtable(htable)
  515.      hashtable * htable;
  516. {
  517.   long count;
  518.   printf("Number of buckets: %ld\n",  htable->number_of_buckets);
  519.   printf("Bucket mask %ld\n", htable->buckets_mask);
  520.   printf("Element Size %ld\n", htable->element_size);
  521.   printf("Number of allocated elements %ld\n", htable->number_of_elements);
  522.   printf("Max number of elements %ld\n", htable->max_number_of_elements);
  523.   
  524.   printf("\nContents:\n");
  525.   for(count = 0; count < htable->number_of_elements; count++){
  526.     print_content_element(count, htable);    
  527.   }
  528.   printf("\nBuckets:\n");
  529.   for(count = 0; count < htable->number_of_buckets; count++){
  530.     if((htable->buckets)[count] != -1)
  531.       print_bucket(count, htable);    
  532.   }
  533. } 
  534.  
  535. /* for saber trials:
  536.  
  537. foo(){
  538. hashtable *htable;
  539. hash_entry entry;
  540. htable = make_hashtable(0, 0, sizeof(hash_entry));
  541. print_hashtable(htable);
  542. put_hash("food", htable, &entry);
  543. print_hashtable(htable);
  544. *get_hash("food", htable);
  545. put_hash("food", htable, &entry);
  546. print_hashtable(htable);
  547. }
  548. */
  549.